package class04

/*
	最长递增子序列，O（N*logN）解法
	要求 返回 一个与原来数组等长的数组，每个数组的含义是，以当前位置为结尾
	最长的递增子序列长度
*/
// O(N^2) 的实现
func getdp1(arr []int) []int {
	dp := make([]int, len(arr))
	dp[0] = 1
	for i:=1; i<len(arr); i++ {
		for j:=i-1; j>=0; j-- {
			if arr[j] < arr[i] {
				dp[i] = dp[j] + 1
				break
			}
			dp[i] = 1
		}
	}
	return dp
}

/*
	算法思路：
		dp   []int
		ends []int
	通过ends数组加速dp数组的生成，
	ends数组，每个i表示，找到所有长度为i+1的递增子序列中最小的结尾是啥
	arr [3, 2, 4, 5, 1, 3]
	dp  [1, 1, 2, 3, 1, 2]
	ends[1, 3, 5]
	1. 那到arr数组中的值
	2. 起初ends没有有效区
	3. 在ends的有效去找到大于等于当前值的数，并替换掉它，该数左边的个数就是dp当前的值
*/
func getdp2(arr []int) []int{
	ends := make([]int, len(arr))
	dp := make([]int, len(arr))
	dp[0] = 1
	ends[0] = arr[0]
	right := 0 // 有效区
	l, r, m := 0, 0, 0

	for i:=0; i<len(arr); i++ {
		l = 0
		r = right
		for l <= r {
			m = (l+r)/2
			if arr[i] > ends[m] {
				l = m + 1
			} else {
				r = m - 1
			}
		}
		// l 即为插入位置
		right = max(right, l)
		ends[l] = arr[i]
		dp[i] = l+1
	}
	return dp
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}